#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 032. 最长有效括号.py
@time: 2022/1/27 12:56
@desc: https://leetcode-cn.com/problems/longest-valid-parentheses/
> 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

@解决方法：
    1. 动态规划
    2. 两种情况：
        a. 当前字符与前一个字符恰好组成一个"()"，则dp[i] = dp[i-2] + 2, 记得考虑i的位置
        b. 当前字符与dp[i-1]-1前的字符(即第i-dp[i-1]-1个)恰好组成一"(......)",则dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
          * 为什么还要加dp[i-dp[i-1]-2]，因为现在有效字符串已经是两个部分：（0, i-dp[i-1]-2), (i-dp[i-1]-1, i)， 所以都要加上

1. Ot(n), Os(n)
'''

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        dp = [0]*(n+1)
        ans = 0
        for i in range(1, n):
            if s[i]==')':
                if s[i-1]=='(':
                    dp[i] = 2 + (dp[i-2] if i>1 else 0)
                elif i-dp[i-1]>0 and s[i-dp[i-1]-1]=='(':
                    dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
                ans = max(ans, dp[i])
        return ans